package com.jhy.review.day04;

import java.util.HashSet;
import java.util.Stack;

/**
 * （深度优先遍历）
 * 1，利用栈实现
 * 2，从源节点开始把节点按照深度放入栈，然后弹出
 * 3，每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
 * 4，直到栈变空
 * 一条路走到黑
 */
public class DFS {
    public static void dfs(Node head){
        if(head == null){
            return;
        }
        // 用栈来实现
        Stack<Node> stack = new Stack<>();
        // 还是用set来代替这个走过的路径
        HashSet<Node> hashSet = new HashSet<>();
        // 深度优先遍历是提前在入栈的时候提前打印，这里是打印操作 你也可以在这里进行其他操作
        System.out.println(head.value);
        while(!stack.isEmpty()){
            Node node = stack.push(head);
            hashSet.add(head);
            // 还是看当前节点的临接节点
            for (Node cur : node.nexts){
                if(!hashSet.contains(cur)){
                    // 用hashset记录这个节点
                    hashSet.add(cur);
                    // 把刚刚栈弹出来的节点在加进来 这样我们就可以保持一条路走到黑了
                    stack.push(node);
                    System.out.println(cur.value);
                    stack.push(cur);
                    // 然后结束这个for循环 就可以不去判断后面那些节点了 保持了之前的顺序
                    break;
                }
            }
        }
    }
}
